package com.xiayuanxing.arithmetic.DataStructures.LinkedList;

import java.util.Stack;

/**
 * @program: arithmetic
 * @description: 单链表（直接添加到链表的尾部，不考虑排序）
 * @author: xia yuan xing
 * @create: 2021-08-31 15:48
 */
public class SingleLinkedListDemo {

    public static void main(String[] args) {
        //测试，创建节点
        HeroNode heroNode1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode heroNode2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode heroNode3 = new HeroNode(3, "吴用", "智多星");
        HeroNode heroNode4 = new HeroNode(4, "林冲", "豹子头");

        //测试创建链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
//        singleLinkedList.add(heroNode1);
//        singleLinkedList.add(heroNode2);
//        singleLinkedList.add(heroNode3);
//        singleLinkedList.add(heroNode4);


        //测试使用第二种加入方法，带排序
        singleLinkedList.addByOrder(heroNode1);
        singleLinkedList.addByOrder(heroNode4);
        singleLinkedList.addByOrder(heroNode2);
        singleLinkedList.addByOrder(heroNode3);
        System.out.println("======原来的链表=======");
        singleLinkedList.list();


//        //测试显示链表
//        singleLinkedList.list();
//        System.out.println("===============链表修改===============");
//        //测试修改节点
//        HeroNode heroNode = new HeroNode(2,"修改测试","修改测试");
//        singleLinkedList.updateLinkedList(heroNode);
//        //显示链表
//        singleLinkedList.list();
//
//        //测试删除节点：删除第一个
//        System.out.println("===============链表删除================");
//        singleLinkedList.deleteHeroNode(1);
//        singleLinkedList.list();

//        //测试求单链表的节点个数
//        System.out.println("有效节点的个数为："+geteffectiveHeroNodeNum(singleLinkedList.getHead()));
//
//        //测试获取倒数第K个节点
//        System.out.println(findLastIndexNode(singleLinkedList.getHead(),2));

//        //测试单链表反转
//        System.out.println("======单链表反转======");
//        reversetList(singleLinkedList.getHead());
//        singleLinkedList.list();

        System.out.println("======从尾到头打印单链表======");
        reversePrint(singleLinkedList.getHead());


    }

    /**
     * 获取有效节点的个数
     * 备注：不统计头节点
     *
     * @param head 链表的头节点
     * @return
     */
    public static int geteffectiveHeroNodeNum(HeroNode head) {
        //判断链表是否为空
        if (head.next == null) {
            //表示节点为空
            return 0;
        }
        //定义一个辅助节点和一个计数器
        int length = 0;
        HeroNode cur = head.next;
        while (cur != null) {
            length++;
            cur = cur.next;
        }
        return length;
    }


    /**
     * 查询单链表中倒数第K个节点
     * 1.编写一个方法，接收head节点，同时接收一个index
     * 2.index：表示是倒数的第index个节点
     * 3.先把链表从头到尾遍历，得到链表的总长度 geteffectiveHeroNodeNum
     * 4.得到size后，开始从链表的第一个开始遍历（size-index）个，就可以得到该节点
     * 5.找到该节点则返回，找不到返回null
     *
     * @param head
     * @param index
     * @return
     */
    public static HeroNode findLastIndexNode(HeroNode head, int index) {
        //判断链表为空
        if (head.next == null) {
            //链表为空
            return null;
        }
        //获取链表的长度
        int size = geteffectiveHeroNodeNum(head);
        //参数校验
        if (index <= 0 || index > size) {
            return null;
        }
        //定义辅助变量，for循环定位到倒数的index
        HeroNode cur = head.next;
        for (int i = 0; i < size - index; i++) {
            cur = cur.next;
        }
        return cur;
    }

    /**
     * 单链表的反转
     *
     * @param head
     */
    public static void reversetList(HeroNode head) {

        //校验链表是否为空或者只有一个节点
        if (head.next == null || head.next.next == null) {
            return;
        }

        //定义一个辅助指针，帮助我们来遍历原来的链表
        HeroNode cur = head.next;
        //指向当前节点【cur】的下一个节点
        HeroNode next = null;
        //创建一个新的头节点
        HeroNode reversetHead = new HeroNode(0, "", "");

        //遍历原来的链表，遍历每一个节点将其取出，并放在新的链表reversetHead的最前端
        while (cur != null) {
            //暂时保存当前节点的下一个节点
            next = cur.next;
            //将cur的下一个节点指向新的链表的最前端
            cur.next = reversetHead.next;
            //将cur连接到新的链表上
            reversetHead.next = cur;
            //将cur后移
            cur = next;
        }
        //将head.next指向 reversetHead.next，实现单链表的反转
        head.next = reversetHead.next;
    }


    //从尾到头打印单链表

    public static void reversePrint(HeroNode head) {
        //非空校验
        if (head.next == null) {
            return;
        }
        //创建一个栈
        Stack<HeroNode> heroNodes = new Stack<>();
        //获取当前节点
        HeroNode cur = head.next;

        //将链表中的节点压入栈中
        while (cur != null) {
            heroNodes.add(cur);
            //后移
            cur = cur.next;
        }

        //出栈
        while (heroNodes.size() > 0) {
            System.out.println(heroNodes.pop());
        }
    }


}


/**
 * @program: arithmetic
 * @description: 定义SingleLinkedList
 * @author: xia yuan xing
 */
class SingleLinkedList {

    /**
     * 初始化一个头节点，头节点不懂，不存放具体数据
     */
    private HeroNode head = new HeroNode(0, "", "");


    /**
     * 获取头节点
     *
     * @return
     */
    public HeroNode getHead() {
        return head;
    }

    /**
     * 添加节点1: 到单向链表 思路：不考虑编号顺序时，找到当前链表的最后节点，将这个节点的next指向新的节点
     *
     * @param heroNode
     */
    public void add(HeroNode heroNode) {
        //创建一个辅助的临时节点temp，因为head节点不能动
        HeroNode temp = head;
        //遍历链表，找到最后
        while (true) {
            if (temp.next == null) {
                break;
            }
            //如果没有找到最后，将temp后移
            temp = temp.next;
        }
        //当退出while循环时，temp就已经指向链表的最后，同时将这个节点指向新的节点
        temp.next = heroNode;
    }

    /**
     * 添加节点2，根据位置添加节点，若该位置存在节点，则添加失败并提示
     *
     * @param heroNode
     */
    public void addByOrder(HeroNode heroNode) {
        //创建辅助节点，要求是：该辅助节点是位于添加位置的前一个节点，否则添加失败
        HeroNode temp = head;
        //标志添加的编号是否存在
        boolean flag = false;
        while (true) {
            if (temp.next == null) {
                //说明temp已经在链表的最后了
                break;
            } else if (temp.next.no > heroNode.no) {
                //说明位置找到了，就在temp后面插入
                break;
            } else if (temp.next.no == heroNode.no) {
                //说明希望添加的节点heroNode.no（编号）已经存在
                flag = true;
                break;
            }
            //temp后移，相当于遍历当前链表
            temp = temp.next;
        }
        //当退出while循环时，判断flag,为true时，表示不能添加，编号已存在，否则可以添加
        if (flag) {
            //表示编号已经存在，不能添加
            System.out.printf("准备插入的数据的编号：%d 已经存在，不能加入\n", heroNode.no);
        } else {
            //插入到链表中，temp的后面
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }


    /**
     * 显示链表
     */
    public void list() {
        //判断链表是否为空
        if ((head.next == null)) {
            System.out.println("链表为空");
            return;
        }
        //头节点不可动，创建辅助节点遍历
        HeroNode temp = head.next;
        while (true) {
            //判断sf到链表最后
            if (temp == null) {
                break;
            }
            //没有到链表最后，输出该链表信息并将节点后移
            System.out.println(temp);
            temp = temp.next;
        }
    }


    /**
     * 修改节点： 根据编号来修改节点，编号不可修改
     *
     * @param heroNode
     */
    public void updateLinkedList(HeroNode heroNode) {
        //判断链表是否为空
        if ((head.next == null)) {
            System.out.println("链表为空");
            return;
        }
        //找到需要修改的节点，根据no编号
        //定义辅助变量temp
        HeroNode temp = head.next;
        //表示是否找到该节点
        boolean flag = false;
        while (true) {
            if (temp == null) {
                //说明已经到链表的最后位置
                break;
            }
            if (temp.no == heroNode.no) {
                //找到了
                flag = true;
                break;
            }
            //节点后移，相当于遍历链表
            temp = temp.next;
        }
        if (flag) {
            temp.name = heroNode.name;
            temp.nickName = heroNode.nickName;
        } else {
            System.out.printf("该节点编号：%d不存在\n", heroNode.no);
        }
    }

    /**
     * 删除节点： 根据编号删除节点
     * 思路：head节点不能动，使用辅助节点找到待删除节点的前一个节点，在比较时，
     * 是temp.next.no和需要删除的节点no比较
     */
    public void deleteHeroNode(int no) {
        //判断链表是否为空
        if ((head.next == null)) {
            System.out.println("链表为空");
            return;
        }
        //定义辅助变量temp
        HeroNode temp = head;
        //表示是否找到待删除节点的前一个节点
        boolean flag = false;
        while (true) {
            if (temp.next == null) {
                //说明已经到链表的最后位置
                break;
            }
            if (temp.next.no == no) {
                //找到了待删除节点的前一个节点
                flag = true;
                break;
            }
            //节点后移，相当于遍历链表
            temp = temp.next;
        }
        if (flag) {
            //删除节点
            temp.next = temp.next.next;
        } else {
            System.out.printf("要删除的节点：%d不存在\n", no);
        }
    }


}

/**
 * 定义HeroNode,每个HeroNode 对象就是一个节点
 */
class HeroNode {
    public int no;
    public String name;
    public String nickName;
    //指向下一个节点
    public HeroNode next;

    //构造器
    public HeroNode(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    /**
     * 重写toString
     *
     * @return
     */
    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}